#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool isValid(string s)
    {
        if (s.size() % 2 == 1) {
            return false;   // 匹配符号一定是偶数,如果是奇数直接返回 False
        }
        // 用来快速匹配右括号对应左括号
        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> cStk;

        for (auto ch : s) {
            // 如果当前栈中已经有了右括号,判断栈顶元素是否是匹配的左括号
            if (pairs.count(ch)) {
                if (cStk.empty() || cStk.top() != pairs[ch]) {
                    return false;
                }
                cStk.pop();
            } else {
                // 如果不是右括号,那肯定是左括号,放入栈顶
                cStk.push(ch);
            }
        }
        return cStk.empty();
    }
};

int main()
{
    cout << "Hello World!" << endl;
    return 0;
}
